# 动态规划50题 https://www.bilibili.com/video/BV1aa411f7uT
# 6/50 打家劫舍
# leetcode第198题: https://leetcode.cn/problems/house-robber/description/

def rob(nums: list[int]) -> int:
    """常规的动态规划算法, 空间复杂度是O(n)"""
    n = len(nums)
    if n < 2:
        return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = nums[1]
    for i in range(2, n):
        # 这里当i = 2时,dp[i - 3]即dp[-1]也就是dp数组的最后一个元素, 由于dp初始化了为0, 所以没有影响
        dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i]

    return max(dp[n - 1], dp[n - 2])


def rob_std(nums: list[int]) -> int:
    """标准解法"""
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1, n):
        if i == 1:
            dp[1] = max(nums[0], nums[1])
        else:
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[n - 1]


def rob_opt(nums: list[int]) -> int:
    """优化的算法, 由于只考虑最后两个元素, 所以只需要迭使用两个变量迭代计算就可以, 空间复杂度为O(1)"""
    # 递推空间优化
    dp0 = 0
    dp1 = 0
    for x in nums:
        dp0, dp1 = dp1, max(dp1, dp0 + x)
    return max(dp0, dp1)


if __name__ == '__main__':
    nums = [1, 2, 3, 1]  # 4
    print(rob_std(nums))
    nums1 = [2, 7, 9, 3, 1]  # 12
    print(rob_std(nums1))
    nums2 = [2, 1, 1, 2]
    print(rob_std(nums2))  # 4
